package medium;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 2007. 从双倍数组中还原原数组
 * 创建时间：2024-04-18 00:11
 */
public class 从双倍数组中还原原数组_2007 {
    /**
     * 大概思路：
     * 将数组先进行排序，
     * 记录num出现的频率，并查找num*2大于0的频率，找到的话将num加入original数组中
     */
    static class Solution {
        public int[] findOriginalArray(int[] changed) {
            int[] original = new int[changed.length / 2];
            Arrays.sort(changed);
            Map<Integer, Integer> fre = new HashMap<>();
            for (int i : changed) {
                fre.put(i, fre.getOrDefault(i, 0) + 1);
            }
            int index = 0;
            for (int i : changed) {
                if (fre.get(i) == 0) {
                    continue;
                }
                fre.put(i, fre.get(i) - 1);
                int d = i * 2;
                if(fre.getOrDefault(d, 0) == 0) {
                    return new int[0];
                }
                fre.put(d, fre.get(i) - 1);
                original[index++] = i;
            }
            return original;
        }
    }
}
